home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / bipl.zip / PROGS.ZIP / CSGEN.ICN < prev    next >
Text File  |  1992-11-26  |  4KB  |  140 lines
  1. ############################################################################
  2. #
  3. #    File:     csgen.icn
  4. #
  5. #    Subject:  Program to generate context-sensitive sentences
  6. #
  7. #    Author:   Ralph E. Griswold
  8. #
  9. #    Date:     June 10, 1988
  10. #
  11. ###########################################################################
  12. #  
  13. #     This program accepts a context-sensitive production grammar
  14. #  and generates randomly selected sentences from the corresponding
  15. #  language.
  16. #  
  17. #     Uppercase letters stand for nonterminal symbols and -> indi-
  18. #  cates the lefthand side can be rewritten by the righthand side.
  19. #  Other characters are considered to be terminal symbols. Lines
  20. #  beginning with # are considered to be comments and are ignored.
  21. #  A line consisting of a nonterminal symbol followed by a colon and
  22. #  a nonnegative integer i is a generation specification for i
  23. #  instances of sentences for the language defined by the nontermi-
  24. #  nal (goal) symbol.  An example of input to csgen is:
  25. #  
  26. #          #   a(n)b(n)c(n)
  27. #          #   Salomaa, p. 11.
  28. #          #   Attributed to M. Soittola.
  29. #          #
  30. #          X->abc
  31. #          X->aYbc
  32. #          Yb->bY
  33. #          Yc->Zbcc
  34. #          bZ->Zb
  35. #          aZ->aaY
  36. #          aZ->aa
  37. #          X:10
  38. #  
  39. #  The output of csgen for this example is
  40. #  
  41. #          aaabbbccc
  42. #          aaaaaaaaabbbbbbbbbccccccccc
  43. #          abc
  44. #          aabbcc
  45. #          aabbcc
  46. #          aaabbbccc
  47. #          aabbcc
  48. #          abc
  49. #          aaaabbbbcccc
  50. #          aaabbbccc
  51. #  
  52. #  
  53. #     A positive integer followed by a colon can be prefixed to a
  54. #  production to replicate that production, making its selection
  55. #  more likely. For example,
  56. #  
  57. #          3:X->abc
  58. #  
  59. #  is equivalent to
  60. #  
  61. #          X->abc
  62. #          X->abc
  63. #          X->abc
  64. #  
  65. #  Option: The -t option writes a trace of the derivations to stan-
  66. #  dard error output.
  67. #  
  68. #  Limitations: Nonterminal symbols can only be represented by sin-
  69. #  gle uppercase letters, and there is no way to represent uppercase
  70. #  letters as terminal symbols.
  71. #  
  72. #     There can be only one generation specification and it must
  73. #  appear as the last line of input.
  74. #  
  75. #  Comments: Generation of context-sensitive strings is a slow pro-
  76. #  cess. It may not terminate, either because of a loop in the
  77. #  rewriting rules or because of the progressive accumulation of
  78. #  nonterminal symbols.  The program avoids deadlock, in which there
  79. #  are no possible rewrites for a string in the derivation.
  80. #  
  81. #     This program would be improved if the specification of nonter-
  82. #  minal symbols were more general, as in rsg.
  83. #  
  84. ############################################################################
  85. #
  86. #  Links: options
  87. #
  88. ############################################################################
  89.  
  90. link options
  91.  
  92. global xlist
  93.  
  94. procedure main(args)
  95.    local line, goal, count, s, opts, deadlock
  96.  
  97.    opts := options(args,"x") 
  98.    deadlock := \opts["x"]
  99.    while line := read() do        #  read in grammar
  100.       if line[1] == "#" then next
  101.       else if xpairs(line) then next
  102.       else {
  103.          line ? (goal := move(1),move(1),count := (0 < integer(tab(0))))
  104.          break
  105.          }
  106.    if /count then stop("no goal specification")
  107.    every 1 to count do {        #  generate sentences
  108.       s := goal
  109.       while upto(&ucase,s) do {        #  test for nonterminal
  110.          if \deadlock then write(&errout,s)
  111.                     #  quit on deadlock
  112.          if not(s ? replace(!xlist)) then break next
  113.          until s ?:= replace(?xlist)    #  make replacement
  114.          }
  115.       write(s)
  116.       }
  117. end
  118.  
  119. #  replace left hand side by right hand side
  120. #
  121. procedure replace(a)
  122.    suspend tab(find(a[1])) || (move(*a[1]),a[2]) || tab(0)
  123. end
  124.  
  125. #  enter rewriting rule
  126. #
  127. procedure xpairs(s)
  128.    local i, a
  129.    initial xlist := []
  130.    if s ? {
  131.                 #  handle optional replication factor
  132.       i := 1(0 < integer(tab(upto(':'))),move(1)) | 1 &
  133.       a := [tab(find("->")),(move(2),tab(0))]
  134.       }
  135.    then {
  136.       every 1 to i do put(xlist,a)
  137.       return
  138.       }
  139. end
  140.